package main

import "math"

/*
和为s的连续正数序列
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]

示例 2：
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
*/
func findContinuousSequence(target int) [][]int {
	// 枚举所有连续数组的情况，比如2个连续，3个连续 *** n个连续
	// target / n 为中间数，中间数前面的数必须比 n/2 多或相等，即：target/x >= x/2
	// 最终可得出 n^2 <= target*2
	var (
		res  = make([][]int, 0)
		sum  int // 当前连续和
		mid  int // 中间数
		l, r int // 左右开始数
		maxN = int(math.Sqrt(float64(target * 2)))
	)
	for n := maxN; n >= 2; n-- {
		mid = target / n

		if n == 2 && target%2 == 0 { // 两个数的和不可能是偶数
			continue
		}

		if n%2 == 0 { //n为偶数
			// 左侧取 n/2-1个，右侧取 n/2 个
			// 偶数情况下，只有这一种取法，证明如下：
			// 如果target不能被n整除，则表明mid比实际结果偏小，只能再右侧取更多的数，这样平均数才会比mid大，使得和符合预期
			// 如果target能被n整除，假如在左侧取更多的数，则平均值比mid小，使得和比target小
			l = mid - (n/2 - 1)
			r = mid + n/2
		} else { // n为奇数，左右各取 n/2 个
			l = mid - n/2
			r = mid + n/2
		}

		sum = (l + r) * n / 2 // 求和公式
		if sum == target {
			t := make([]int, r-l+1)
			for i := l; i <= r; i++ {
				t[i-l] = i
			}
			res = append(res, t)
		}
	}

	return res
}

func main() {

}
